package leetcode_2501_2600;

import javax.swing.*;

public class LeeCode_2556 {
    public static void main(String[] args) {
        System.out.println(isPossibleToCutPath(new int[][]{{1, 1, 1}, {1, 0, 1}, {1, 1, 1}}));
        System.out.println(isPossibleToCutPath(new int[][]{{1, 1}}));
    }
    private static boolean isPossibleToCutPath(int[][] grid) {
        return !dfs(grid, grid.length, grid[0].length, 0, 0) || !dfs(grid, grid.length, grid[0].length, 0, 0);
    }
    private static boolean dfs(int[][] grid, int m, int n, int x, int y){
        if (x == m - 1 && y == n - 1)
            return true;
        grid[x][y] = 0;
        return (x + 1 < m && grid[x + 1][y] > 0 && dfs(grid, m, n, x + 1, y)) ||
                (y + 1 < n && grid[x][y + 1] > 0 && dfs(grid, m, n, x, y + 1));
    }
}
